package com.miroshnichenko.binarytree;

public class BinaryTree<E extends Comparable<E>> {
    private Node rootElement;

    private class Node {
        private E element;
        private Node left;
        private Node right;

        Node(E element) {
            this.element = element;
        }

        void add(E e) {
            if (this.element.compareTo(e) > 0) {
                if (right == null) right = new Node(e);
                else right.add(e);
            } else {
                if (left == null) left = new Node(e);
                else left.add(e);
            }
        }

        E remove(E element) {
            //ToDo: remove
            return null;
        }

        boolean hasElement(E element) {
            if (this.element.compareTo(element) == 0) return true;

            if (this.element.compareTo(element) > 0 && right != null) {
                return right.hasElement(element);
            }
            if (this.element.compareTo(element) < 0 && left != null) {
                return left.hasElement(element);
            }
            return false;
        }

        E findElement(E element) {
            if (this.element.compareTo(element) == 0) return this.element;

            if (this.element.compareTo(element) > 0 && right != null) {
                return right.findElement(element);
            }
            if (this.element.compareTo(element) < 0 && left != null) {
                return left.findElement(element);
            }
            return null;
        }

        void printInDeep() {
            if (left != null) left.printInDeep();
            System.out.println(this);
            if (right != null) right.printInDeep();
        }

        void printInWidth(int currentDeep, int requireDeep) {
            if (currentDeep == requireDeep) {
                System.out.print(element + " ");
            } else {
                currentDeep++;
                if (left != null) left.printInWidth(currentDeep, requireDeep);
                if (right != null) right.printInWidth(currentDeep, requireDeep);
            }
        }

        int getMaxDeep(int currentDeep) {
            int maxRightDeep = currentDeep;
            int maxLeftDeep = currentDeep;

            currentDeep++;

            if (left != null) maxLeftDeep = left.getMaxDeep(currentDeep);
            if (right != null) maxRightDeep = right.getMaxDeep(currentDeep);

            return (maxLeftDeep < maxRightDeep) ? maxRightDeep : maxLeftDeep;
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    public void add(E element) {
        if (rootElement == null) {
            rootElement = new Node(element);
        } else {
            rootElement.add(element);
        }
    }

    public E remove(E element) {
        if (rootElement == null) return null;
        return rootElement.remove(element);
    }

    public boolean hasElement(E element) {
        return rootElement != null && rootElement.hasElement(element);
    }

    public E findElement(E element) {
        if (rootElement == null) return null;
        return rootElement.findElement(element);
    }

    public void printInDeep() {
        rootElement.printInDeep();
    }

    public void printInWidth() {
        if (rootElement == null) return;

        int deep = rootElement.getMaxDeep(0);

        System.out.println("Deep -> " + deep + "\n");

        while (deep >= 0) {
            rootElement.printInWidth(0, deep--);
            System.out.println();
        }
    }
}
